COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\input macro[1,mps]
C00029 ENDMK
C⊗;
\input macro[1,mps]
\input macrwf[1,mps]
\magnification\magstephalf
\def\C{\hbox{C}}
\noindent Chapter 2

If $f$ is a self-inverse function, $f\circ f = I$, and $\rho$ is any relation, 
the conjugate relation $\rho$* is $f\circ\rho\circ f$.  Properties of
conjugation include:
$$\eqalign{I↑* & = f\circ I\circ f = f\circ f = I\cr
\rho↑*\circ\sigma↑* & = f\circ\rho\circ f\circ f\circ\sigma\circ f = (\rho\circ
\sigma)↑*\cr
(\rho↑*)↑- & = (f\circ\rho\circ f)↑- = f↑-\circ\rho↑-\circ f↑- = (\rho↑-)↑*\cr}$$
Examples:  $f$ reverses a string.  $f$ maps a number into its negative, or its
reciprocal, or its negative reciprocal.  $f$ maps an $n$tuple into its reverse.

\noindent Device:

A component that can hold information, test it, and modify it.  The {\it carrier}
of a device is the set of values it may contain.  An element of the carrier
is called a {\it state} of the device.  The {\it repertory} of a device is
a set of (partial) functions available to map one state of the device into
the next.

An element of the repertory is called an {\it operation} of the device.

A {\it test} is an operation that is a partial identity function, 
$I\cap(S\times S)$ where $S$ is a subset of the carrier.

\noindent Machine:

A machine $M$ is a finite set of devices.  It has a set $X↓M$ of {\it arguments},
and a set $Y↓M$ of {\it results}.  A Machine is used to compute relations
from $X↓M$ to $Y↓M$.

\noindent Configuration:

A mapping of each device in a machine to a state of that device.  The
aggregate of information in a machine at a particular instant.

\noindent Initial Relation:

A machine $M$ has an {\it initial relation} $\alpha$ (typically a function)
relating members of $X↓M$ to compatible initial configuration of $M$.  One
can express $\alpha$ as a separate initial relation for each device:
$$x\alpha \langle S↓1, S↓2,\ldots, S↓n\rangle \Leftrightarrow x\alpha↓d S↓d$$
\noindent Final Relation:

A machine $M$ has a {\it final relation} $\omega$ (typically a function)
relating members of $Y↓M$ to compatible final configurations of $M$.  One
can express $\omega$ as a separate final relation for each device:
$$y\omega \langle S↓1, S↓2, \ldots, S↓n\rangle \Leftrightarrow y \omega↓d S↓d$$
\noindent Instruction:

An {\it instruction} of a machine relates each device of the machine to an
operation of that device.  If each device $D↓i$ is in state $x↓i$ in a 
configuration $\C = \langle x↓1, x↓2,\ldots, x↓k \rangle$ and an instruction
$\langle f↓1, f↓2, \ldots, f↓k \rangle$ assigns operation $f↓i$ to $D↓i$, the
instruction relates \C\ to $\C' = \langle x↓1f↓1, x↓2f↓2,\ldots, x↓kf↓k\rangle$.

\noindent Program:

A {\it program} $P$ for machine $M$ is a finite set of instructions for $M$.
A {\it partial history} of $P$ for argument $x\in X↓M$ is a sequence 
$x\alpha↓M \C↓0\Pi↓1 \C↓1 \Pi↓2\ldots\Pi↓n\C↓n (n \geq 0)$, where each
$\Pi↓i\in P$ and each $\C↓i\Pi = \C↓{i+1}$.  A {\it history} of $P$ for
argument $x\in X↓M$ and result $y\in Y↓M$ is a sequence
$$\langle x,\alpha↓M, \C↓0,\Pi↓1, \C↓1, \Pi↓2,\ldots,\Pi↓n, \C↓n, \omega↑{-1}↓M, 
y\rangle$$
This sequence shows that $\langle x\alpha↓M, y \omega↓M\rangle$ belongs to
the relation $\Pi↓1\circ\Pi↓2\circ\ldots\circ\Pi↓n \langle\Pi↓1, \Pi↓2,\ldots,
\Pi↓n\rangle$ is called a {\it computation} of $P$ for argument $x$ and result
$y$.  The sequence of configurations $\langle \C↓0, \C↓1,\ldots, \C↓n\rangle$ is
called a {\it trace} of $P$ (for $x$ and $y$).  The relation $\tau =\alpha↓M
\Pi↑*\omega↑{-1}↓M$ is called the {\it transfer relation} of $P$.  Similarly,
there are {\it partial traces} and {\it partial computations}.

\noindent Determinism:

In general, there may be more than one instruction applicable to a configuration,
or an instruction and the final relation may both be applicable.  In that
situaton, there is more than one way to extend a partial computation to a
longer (partial or complete) computation.  This situation arises when two
instructions $\langle\mu↓1, \mu↓2,\ldots, \mu↓n\rangle$ and $\langle\nu↓1,
\nu↓2,\ldots, \nu↓n\rangle$ have overlapping domains, operation by operation,
or when instruction $\langle\mu↓1, \mu↓2, \ldots, \mu↓n\rangle$ and final
relation $\langle\omega↓1, \omega↓2,\ldots, \omega↓n\rangle$ have {\it overlapping}
domains.  When no such overlap occurs, a program is caled deterministic.  A
deterministic program has at most one complete computation for each
argument, and its transfer relation is a partial function.  (The converse need
not be true.)

\noindent Blocking:

A configuration is {\it blocked} if it is not in the domain of any instruction,
nor in the domain of $\omega$.  A partial computation that reaches a blocked
configuration obviously can not be extended to a complete, or a longer partial,
computation.

\noindent Transducer:

A program for a machine with one input device and one output device, where
$\alpha↓{input} = I↓{\Gamma↑{*}}$, $\omega↓{output} = I↓{\Delta↑{*}}$.

\noindent Transfer Relation of Transducer:
$$\tau = \alpha\pi↑*\omega$$
A common application of programs is to test whether a string input is in a 
certain set (language).  Let $L$ be the language.  One convention for such
a program is that the transition relation holds between a string in $L$ and a
particular result, called {\tt ACCEPT} and (possibly) synonymous with {\tt TRUE}.
The transition relation does not hold between a string not in $L$ and the
result {\tt ACCEPT}.

For an input string in $L$, there may be more than one partial or complete
computation.  So long as there is at least one complete computation with
result {\tt ACCEPT}, the string is {\it accepted}; there may be other
computations, whether completed, infinite, or blocked.  In this convention,
we say the program {\rm accepts} the language.  Symbolically, 
$x\in L\Leftrightarrow x \tau↓p\ {\tt ACCEPT}$.

A second convention requires that the program be non-blocking, deterministic,
and give a result for every input string.  The transition relation, a
function, holds between any string in the language and a particular result,
called {\tt ACCEPT}.  The transition function also holds between any string
not in the language and another particular result, called {\tt REJECT}, which is
possibly synonymous with {\tt FALSE}.  Because the computation is completed for
every input, we know that every storage device $d$ returns to its standard
state, which is related by $\omega↓d$ both to {\tt ACCEPT} and to {\tt REJECT}.
In the absence of an output device, the final control states must be partitioned
into {\it accepting} states in $\omega↓{control}\circ {\tt ACCEPT}$ and
{\it rejecting} states in $\omega↓{control}\circ {\tt REJECT}$.

In this convention, we say a program {\it recognizes} $L$.  Symbolically,
$$x\in L \Leftrightarrow x\tau↓p\, {\tt ACCEPT}$$
\noindent and
$$ x \notin L \Leftrightarrow x \tau↓p\, {\tt REJECT}.$$
By interchanging {\tt ACCEPT} and {\tt REJECT}, we see that a language is
recognized by (some program for) a machine iff its complement is recognized.

The recognition convention can be generalized to classifying strings.  A
recognizer classifies all input strings into two classes.  A {\it classifier} is
a non-blocking deterministic program that classifies all input strings into a
finite number of classes.  For example, a classifier that determines the
remainder modulo 3 of a binary number is

In our graphic convention, an accepting state of an acceptor is shown as

The final states of a recognizer are shown as

The final states of a classifier similarly might be shown as

We may use a nondeterministic program to generate arbitrary members of a
language.  Let $L$ be the language.  Our convention is that the transition
relation holds between a particular argument, called {\tt ACCEPT} [?] and
(possibly) synonymous with {\tt TRUE}.  The transition relation does not hold
between {\tt ACCEPT} and a string not in $L$.  Strings printed by infinite or
blocked computations are not considered to be generated by those partial
computations.  In this convention, we say the program {\it generates} the
language.  Symbolically, $x\in L \Leftrightarrow {\tt ACCEPT}\, \tau↓p x$.  A
generator for a language containing more than one string will of course be
nondeterministic.

An acceptor for a language is easily converted into a generator for the same
language, replacing each {\tt SCAN A} by {\tt WRITE A}.  Therefore the
languages accepted by a machine (i.e., by some program for that machine) are
the same as those generated by that machine.  The languages recognized by
(programs for) a machine are {\it ipso facto} accepted by the machine, but
for some machines there are languages which have acceptors but not recognizers.

A program for a machine with both input and output is called a {\it filter} if
the only input and output operations are paired, with scan A accompanied by write A.
The transition relation is then a subset $I↓L$ of the identity relation,
and we call the program a filter for $L$.  By omitting the input or the output
operations, we have a generator or an acceptor for $L$, so the same languages
are accepted, generated, and filtered by (programs for) a machine.

Say $x\in L$, $y \in L$

\noindent {\it Acceptor}

\settabs\+$x\alpha$&\cr
\+ $x\alpha$&\quad $\langle{\rm control}:Q↓{\rm start};{\rm input}:x;
{\rm storage}:\Lambda;{\rm output}:\Lambda\rangle \pi↑*$\cr
\+&\quad$\langle{\rm control}:Q↓{\rm accept};{\rm input}:\Lambda;{\rm storage}:
\Lambda;{\rm output}:\Lambda\rangle\omega\, {\tt ACCEPT}$\cr

\noindent {\it Generator}

\settabs\+${\tt START}\alpha$&\cr
\+${\tt START}\alpha$&\quad$\langle{\rm control}: Q↓{\rm start};
{\rm input}:\Lambda;{\rm storage}:\Lambda;{\rm output}:\Lambda\rangle \pi↑*$\cr
\+&\quad $\langle {\rm control}:Q↓{\rm accept};{\rm input}:\Lambda;{\rm storage}:
\Lambda;{\rm output}:x\rangle\omega x$\cr

\noindent {\it Filter}

\settabs\+$x\alpha$&\cr
\+$x\alpha$&\quad$\langle{\rm control}:Q↓{\rm start};{\rm input}:x;
{\rm storage}:\Lambda;{\rm output}:\Lambda\rangle\pi↑*$\cr
\+&\quad$\langle {\rm control}:Q↓{\rm accept};{\rm input}:\Lambda;{\rm storage}:
\Lambda;{\rm output}:x\rangle\omega x$\cr

\noindent{\it Recognizer}

\settabs\+$x\alpha$&\cr
\+$x\alpha$&\quad$\langle{\rm control}:q↓{\rm start};{\rm input}:x;
{\rm storage}:\Lambda;{\rm output}:\Lambda\rangle\pi↑*$\cr
\+&\quad$\langle{\rm control}:Q?q↓{\rm accept};{\rm input}:\Lambda;{\rm storage}:
\Lambda;{\rm output}:\Lambda\rangle\omega\, {\tt ACCEPT}$\cr

\+$y\alpha$&\quad$\langle{\rm control}:q↓{\rm start};{\rm input}:y;
{\rm storage}:\Lambda;{\rm output}:\Lambda\rangle\pi↑*$\cr
\+&\quad$\langle{\rm control}:Q?q↓{\rm reject};{\rm input}:\Lambda;{\rm storage}:
\Lambda;{\rm output}:\Lambda\rangle\omega\,{\tt REJECT}$\cr

\noindent In short,

\noindent {\it Accepter}:

\qquad$\langle Q↓{\rm START}, x, {\rm etc}.\rangle\pi↑* \langle Q↓{\rm ACCEPT},
\Lambda, {\rm etc}.\rangle$

\noindent {\it Generator}:

\qquad$\langle Q↓{\rm start}, \Lambda, {\rm etc}.\rangle\pi↑*\langle 
Q↓{\rm ACCEPT}, x, {\rm etc}.\rangle$

\noindent {\it Filter}

\qquad$\langle Q↓{\rm START}, x, \Lambda, {\rm etc}.\rangle\Pi↑*\langle 
Q↓{\rm ACCEPT}, \Lambda, x, {\rm etc}.\rangle$

\noindent {\it Recognizer}

\qquad$\langle q↓{\rm start}, x, {\rm etc}.\rangle \Pi↑*\langle Q↓{\rm ACCEPT}, 
\Lambda, {\rm etc}.\rangle$
\qquad$\langle q↓{\rm start}, y, {\rm etc}.\rangle\Pi↑*\rangle Q↓{\rm REJECT},
\Lambda, {\rm etc.}\rangle$

Convention:\qquad $i\qquad\qquad↑{\rm CLEANUP}\qquad\qquad j$ \qquad is an 
abbreviation for a set of instructions that returns all storage devices to 
their initial states, such as:

A cleanup may be expected to consume all remaining input as well:

One part of the theory of computability is determining whether programs for one
machine can do everything that programs for another machine can do.  Ignoring
for the moment the practical considerations like differences in speed, we ask
whether every program for one machine can be translated into a program for 
the other, with the same transfer relation.  We also ask whether the translation
preserves such desirable features as determinacy, freedom from blocking, and
freedom from infinite partial computations.\footnote*{In later chapters we
address the possibility that there might be translations, but no algorithm
to find them.} 

Let $P$ be a program for machine $M$, and $M'$ be another machine.  It is known
that there is no {\it general} way to prove that a program $P'$ for $M'$ has the
same transfer function as $P$, nor is there any {\it general} way to determine
if such a $P'$ exists.  By ``general'', we mean a method that always works.  
The chapter on decidability shows how the nonexistence of general methods for 
a class of problems can be demonstrated, but for the moment we want to deal
with some specific problems for which known methods work.

When program $P'$ achieves the same transfer relation as program $P$ by in 
some sense imitating the computations of $P$, we say that $P'$ {\it simulates} 
$P$.  Typically, computations of $P'$ enter configurations some of which imply the
consecutive configurations of $P$.  In such a situation, we say that selected
configurations of $P'$ {\it represent} the configurations of $P$, and we give
a function $\rho$ that relates some configurations of $P'$ to the configurations
of $P$ that they represent.  Our proofs that $P'$ has the same transfer
relation as $P$ will all be based on simulation by representation.

We will present two methods of showing simulation by representation, which we call
the {\it practical} method and the {\it general} method.  The general method is
easy to describe, but tedious to carry out, so examples of its applicaion will
be found in an appendix to the chapter.

The general method of showing that $P$ and $P'$ have the same transfer relation,
$\tau = \tau '$, bisects the problem into showing $\tau \subset\tau '$ and
$\tau '\subset\tau$.  To show, say, that $\tau\subset\tau '$, we show that
$\alpha\Pi↑*\omega\subset\alpha '\Pi '↑* \omega '$.  We want to show
that if
$$x\alpha \C↓0 \Pi \C↓1 \Pi\ldots\Pi \C↓n\omega y$$
is a computation of $P$, then there is a computation
$$x\alpha ' \C'↓0\Pi '↑* \C'↓1\Pi '↑*\ldots\Pi '↑* \C'↓n\omega ' y$$
(notice that the named configurations may be widely separated, or repeated, in the
computation of $P'$), where $\C'↓i \rho \C↓i$.  Diagrammatically, we want to
show that if the left column of the diagram below exists (a computation of $P$),
then there is a corresponding right column (a computation of $P'$, with some
detail possibly omitted), with the exhibited configurations of the right
column representing all the configurations of the left column.

We show this by showing we can add successive rectangles to the diagram, starting
with only the top and left side.  First we show that $\C'↓0$ can be found for which

For any $x$, program $P'$ can select an initial configuration and possibly perform
several instructions on it to reach a configuration $P'↓0$ that represents the
initial configuration of $P↓0$.  In the notation of the relational calculus,
$$\alpha\subset\alpha'\circ\Pi'↑*\circ\rho.$$
Next we show that if $\C'↓i\rho \C↓i\Pi \C↓{i+1}$, i.e. we have a configuration
$\C'↓i$ that represents $\C↓i$ with sequel $\C↓{i+1}$

then $\C'↓{i+1}$ can be found for which

Program $P'$ can perform (possibly zero) instructions on $\C'↓i$ to reach a
$\C'↓{i+1}$ that represents $\C↓{i+1}$.  Or simply $\rho\Pi\subset\Pi'↑*\rho$.
This proof is usually done by case analysis on the instruction of $P$ that is
applied.

By induction on the length of the conputation, we can complete the diagram down to

To validate the last box of the diagram, we must show that instructions of
program $P'$ can change $\C'↓n$ into a terminal configuration that yields the
result $y$.

In a formula, $\rho\omega\subset\Pi'↑*\omega'$.
\bye